package com.zheng.coderepo.algorithm;

import org.junit.Assert;
import org.junit.Test;

/**
 * 猴子第一天摘了若干个桃子，当即吃了一半，还不解馋，又多吃了一个；
 * 第二天，吃剩下的桃子的一半，还不过瘾，又多吃了一个；
 * 以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了。
 * 问第一天共摘了多少个桃子？
 * Created by zcz on 2018/5/21.
 */
public class MonkeyEat {

    /**
     * 把问题回溯分析。令d(1)为第一天剩下的桃子，d(2)为第二天剩下的桃子，。。。d(n)为第二天剩下的桃子.
     * 那么，第一天剩下的桃子=第二天剩下的桃子/2-再吃多一个。即：d1=(d2/2)-1。
     * 换成数据公式：d(n-1)=(d(n)/2)-1.
     */
    public int eat01(int n) {
        int num = 1;
        for (int i = 2; i <= n; i++) {
            num = 2 * num + 2;
        }
        return num;
    }

    @Test
    public void testEat01() {
        int num = eat01(10);
        Assert.assertTrue(num == 1534);
    }
}
